package com.atguigu.linklist;

public class Partition {
    public static ListNode partitionList(ListNode head,int key){
        if(head==null)return null;
        if(head.next==null) return head;
        ListNode cur=head;
        int length=0;
        while(cur!=null){
            cur=cur.next;
            length++;
        }
        int[] a=new int[length];
        cur=head;
        int i=0;
        while(cur!=null){
            a[i]=cur.val;
            cur=cur.next;
            i++;
        }
        int left=-1;
        int right=length;
        for(i=0;i<right;){
            if(a[i]<key){
                swap(a,i,left+1);
                i++;
                left++;
            }else if(a[i]>key){
                swap(a,i,right--);
                right--;
            }else{
                i++;
            }
        }
        cur=head;
        for(i=0;i<length;i++){
            ListNode node=new ListNode(a[i]);
            cur.next=node;
            cur=node;
        }
        return head;
    }
    public static void swap(int[] a,int i,int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
    //不用额外空间
    public static ListNode partitionList2(ListNode head,int pivot){
        ListNode LessStart=null;
        ListNode LessEnd=null;
        ListNode EqualStart=null;
        ListNode EqualEnd=null;
        ListNode MoreStart=null;
        ListNode MoreEnd=null;
        if(head==null) return null;
        if(head.next==null) return head;
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<pivot){  //小于pivot
                if(LessStart==null && LessEnd==null){
                    LessStart=cur;
                    LessEnd=cur;
                }else{
                    LessStart.next=cur;
                    LessEnd=cur;
                }
                cur=cur.next;
            }else if(cur.val==pivot){
                if(EqualStart==null && EqualEnd==null){
                    EqualStart=cur;
                    EqualEnd=cur;
                }else{
                    EqualStart.next=cur;
                    EqualEnd=cur;
                }
                cur=cur.next;
            }else{
                if(MoreStart==null && MoreEnd==null){
                    MoreStart=cur;
                    MoreEnd=cur;
                }else{
                    MoreStart.next=cur;
                    MoreEnd=cur;
                }
                cur=cur.next;
            }
        }
        //小于区为空，等于区，大于区不为空
        if(LessStart==null && EqualStart!=null && MoreStart!=null){
            EqualEnd.next=MoreStart;
            MoreEnd.next=null;
            return EqualStart;
        }else if(LessStart==null && EqualStart!=null && MoreStart==null){ //小于区为空，等于区不为空，大于区为空
            EqualEnd.next=null;
            return EqualStart;
        }else if(LessStart==null && EqualStart!=null && MoreStart!=null){// 空 不 不
            EqualEnd.next=MoreStart;
            MoreEnd.next=null;
            return EqualStart;
        }else if(LessStart!=null && EqualStart!=null && MoreStart!=null){ //不 不 不
            LessEnd.next=EqualStart;
            EqualEnd.next=MoreStart;
            MoreEnd.next=null;
            return LessStart;
        }else if(LessStart!=null && MoreStart!=null &&EqualStart==null){
            LessEnd.next=MoreStart;
            MoreEnd.next=null;
            return LessStart;
        }else if(LessStart!=null && EqualStart!=null && MoreStart==null){ //不  不  空
            LessEnd.next=EqualStart;
            EqualEnd.next=null;
            return LessStart;
        }else{
            LessEnd.next=null;
            return LessStart;
        }
    }
}
